#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;

int gcd(int a, int b) { // 计算a与b的最大公因数
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int modpow(int a, int b, int n) { // 计算a的b次方模n的值
    int c = 1, d = a;
    while (b > 0) {
        if (b % 2 == 1) {
            c = (c * d) % n;
        }
        d = (d * d) % n;
        b /= 2;
    }
    return c;
}

bool is_prime(int n) { // 判断n是否为素数
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int get_prime(int min, int max) { // 随机得到一个min到max之间的素数
    bool flag;
    int p;
    do {
        p = rand() % (max - min + 1) + min;
        flag = is_prime(p);
    } while (!flag);
    return p;
}

void ElGamal() {
    srand(time(NULL)); // 随机数种子
    int p = get_prime(100, 200); // 随机得到一个100到200之间的素数
    int g = 2; // 取g=2
    int x = rand() % (p - 2) + 1; // 随机选取私钥x
    int y = modpow(g, x, p); // 计算公钥y
    cout << "选取的素数p为：" << p << endl;
    cout << "基本元素g为：" << g << endl;
    cout << "私钥x为：" << x << endl;
    cout << "公钥y为：" << y << endl;
    int k = rand() % (p - 2) + 1; // 随机选取一个小于p-1的数作为k
    int m = 123456; // 要加密的明文
    int a = modpow(g, k, p); // 计算密文a
    int b = (m * modpow(y, k, p)) % p; // 计算密文b
    cout << "要加密的明文m为：" << m << endl;
    cout << "选取的随机数k为：" << k << endl;
    cout << "加密后得到的密文a为：" << a << endl;
    cout << "加密后得到的密文b为：" << b << endl;
    int xm = (b * modpow(a, p - 1 - x, p)) % p; // 解密得到明文
    cout << "解密后得到的明文xm为：" << xm << endl;
}